package day15;

import java.util.Arrays;

/**
 * 给定数组people。people[i]表示第 i个人的体重，船的数量不限，每艘船可以承载的最大重量为limit。
 * <p>
 * ,的重量之和最多为limit。
 * <p>
 * 返回 承载所有人所需的最小船数。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：people = [1,2], limit = 3
 * 输出：1
 * 解释：1 艘船载 (1, 2)
 * 示例 2：
 * <p>
 * 输入：people = [3,2,2,1], limit = 3
 * 输出：3
 * 解释：3 艘船分别载 (1, 2), (2) 和 (3)
 * 示例 3：
 * <p>
 * 输入：people = [3,5,3,4], limit = 5
 * 输出：4
 * 解释：4 艘船分别载 (3), (3), (4), (5)
 */
public class Solution1 {
    public int numRescueBoats(int[] people, int limit) {
        int count = 0;
        int len = people.length;
        Arrays.sort(people);
        int left = 0, right = len - 1;
        while (left <= right) {
            if (people[left] + people[right] > limit) {
                count++;
                right--;
            } else if (people[left] + people[right] <= limit) {
                count++;
                right--;
                left++;
            }
        }
        return count;
    }
}
